`
https://leetcode.cn/problems/word-break-ii/
`

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
var wordBreak = function (s, wordDict) {
  const wordSet = new Set(wordDict)
  const memo = new Map()

  function dp(i) {
    const res = [];
    if (i === s.length) {
      res.push("");
      return res;
    }
    // 防止冗余计算
    if (memo.has(i)) {
      return memo.get(i);
    }

    // 遍历所有 s[i...] 的前缀
    for (let j = i + 1; j <= s.length; j++) {
      const prefix = s.substring(i, j)
      // 看看哪些前缀存在 wordDict 中
      if (wordSet.has(prefix)) {
        // 找到一个单词匹配 s[i..i+len)
        const suffixList = dp(j);
        // 构成 s[i+len..] 的所有组合加上 prefix 
        // 就是构成构成 s[i] 的所有组合
        suffixList.forEach((suffix) => {
          const space = suffix === "" ? "" : " ";
          res.push(prefix + space + suffix);
        });
      }
    }
    // 存入备忘录
    memo.set(i, res);

    return res;
  }

  return dp(0)
};